package com.guiwu.caiguanlin.writeTest;


import com.guiwu.caiguanlin.entity.TreeNode;

import java.util.*;

/**
 * 获取全部叶子节点数据
 */
public class TreeDemo {

    public static void main(String[] args) {
        //获取数据
        List<TreeNode> nodeData = getNodeData();
        //构建树
        List<TreeNode> tree = buildTree(nodeData);
        //获取叶子节点数据
        List<TreeNode> leaf = getAllOfLeafNodes(tree);
        leaf.stream().sorted(Comparator.comparing(TreeNode::getId)).forEach(System.out::println);
    }

    //获取全部叶子节点数据
    public static List<TreeNode> getAllOfLeafNodes(List<TreeNode> tree) {
        return recursion(tree, new ArrayList<>());
    }

    //递归获取叶子节点数据
    private static List<TreeNode> recursion(List<TreeNode> tree, List<TreeNode> list) {
        for (TreeNode treeNode : tree) {
            if (treeNode.getChildren() == null || treeNode.getChildren().size() == 0) {
                list.add(treeNode);
                continue;
            }
            recursion(treeNode.getChildren(), list);
        }
        return list;
    }

    /**
     * 构建树，双重循环
     *
     * @return
     */
    public static List<TreeNode> buildTree(List<TreeNode> nodeData) {
        List<TreeNode> list = new ArrayList<>();
        if (nodeData == null || nodeData.size() == 0) {
            return list;
        }
        //双重循环构建树
        for (TreeNode firstCycle : nodeData) {
            if (firstCycle.getParentId() == null) {
                list.add(firstCycle);
            }
            for (TreeNode secondCycle : nodeData) {
                if (!Objects.equals(firstCycle.getId(), secondCycle.getParentId())) {
                    continue;
                }
                if (firstCycle.getChildren() == null) {
                    firstCycle.setChildren(new ArrayList<>());
                }
                firstCycle.getChildren().add(secondCycle);
            }
        }
        return list;
    }

    /**
     * 构建树，优化版
     *
     * @return
     */
    public static List<TreeNode> buildTree2() {
        //获取数据
        List<TreeNode> nodeData = getNodeData();
        List<TreeNode> list = new ArrayList<>();
        if (nodeData == null || nodeData.size() == 0) {
            return list;
        }

        // 使用HashMap优化查找性能
        Map<Object, TreeNode> nodeMap = new HashMap<>();
        for (TreeNode node : nodeData) {
            nodeMap.put(node.getId(), node);
        }

        for (TreeNode node : nodeData) {
            Object parentId = node.getParentId();
            // 检查是否为根节点
            if (parentId == null) {
                list.add(node);
                continue;
            }
            // 直接从Map中查找父节点，避免二次遍历
            TreeNode parent = nodeMap.get(parentId);
            if (parent != null) {
                // 安全添加子节点
                if (parent.getChildren() == null) {
                    parent.setChildren(new ArrayList<>());
                }
                parent.getChildren().add(node);
            }
        }
        return list;
    }

    /**
     * 获取树节点数据
     *
     * @return
     */
    private static List<TreeNode> getNodeData() {
        List<TreeNode> list = new ArrayList<>();
        list.add(new TreeNode(1, "节点1", null, null));
        list.add(new TreeNode(2, "节点2", null, null));
        list.add(new TreeNode(3, "节点3", 1, null));
        list.add(new TreeNode(4, "节点4", 1, null));
        list.add(new TreeNode(5, "节点5", 3, null));
        list.add(new TreeNode(6, "节点6", 5, null));
        list.add(new TreeNode(7, "节点7", 2, null));
        list.add(new TreeNode(8, "节点8", 7, null));
        return list;
    }
}
